/*
将prices[i + 1] - prices[i]作为一个元素排成新的array
对该array求最大子序列和即可(kadane algorithm)

kadane algorithm
依次求以array[i]为结尾的子序列的最大和，即为max_sum_endwith[i]
max_sum_endwith[i+1] = max(max_sum_endwith[i] + array[i+1], array[i+1])
max_sum_subarray = max(max_sum_endwith)
*/

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int maxProfit(vector<int>& prices)
    {
        if(prices.empty())
            return 0;
        int current_max, global_max;
        current_max = global_max = 0;
        for (int i = 0; i < prices.size() - 1; i++) {
            current_max = max(current_max + prices[i + 1] - prices[i], prices[i + 1] - prices[i]);
            if (current_max > global_max)
                global_max = current_max;
        }
        return global_max;
    }
};

int main(int argc, char const* argv[])
{
    Solution temp;
    int a[6] = { 7, 1, 5, 3, 6, 4 };
    vector<int> nums(a, a + 6);
    temp.maxProfit(nums);
    return 0;
}